Semantic class construction discovers peer or sibling relationships among terms or phrases by organizing the terms or phrases into semantic classes. Semantic classes are typically used by a search engine in response to a query to categorize potential responses to the query. For example, {red, white, black . . . } is a semantic class consisting of color instances. Existing methods have typically used a pattern-based approach for semantic class discovery. In a pattern-based approach, predefined patterns are applied to a collection of web pages or used by an online web search engine to produce raw semantic classes (RASCs). Predefined patterns identify certain semantic class categories ahead of time and apply those categories to information in the collection of web pages. However, RASCs are typically noisy and incomplete, and therefore are not treated as usable semantic classes. In addition, the information of one semantic class may be distributed in many RASCs. This issue of multi-membership in which one item may belong to multiple different raw semantic classes has very limited support in existing pattern-based approaches. For example, in a typical pattern based approach, RASCs are labeled according to the predefined patterns. RASCs with the same labels (or hypernyms) are merged to generate the ultimate semantic classes. This is problematic, because some RASCs may not have accurate hypernyms and, in some cases, a RASC may not have a hypernym at all. The inaccuracy and/or lack of hypernyms in existing pattern based approaches not only creates lower quality search results, but also makes it difficult to identify the multi-membership semantic classes.